翻訳と辞書 Words near each other ・ Universal gateway ・ Universal generalization ・ Universal Genève ・ Universal geometric algebra ・ Universal grammar ・ Universal graph ・ Universal Graphics Module ・ Universal Great Brotherhood ・ Universal grinder ・ Universal Groove ・ Universal Gym Equipment ・ Universal Hall ・ Universal Hall Pass ・ Universal Handy Interface ・ Universal Hartland Visual Effects ・ Universal hashing ・ Universal HD ・ Universal health care ・ Universal Health Care Foundation of Connecticut ・ Universal health coverage by country ・ Universal Health Services ・ Universal Helicopters ・ Universal Hero ・ Universal Hint System ・ Universal Hip Hop Parade ・ Universal history ・ Universal History (disambiguation) ・ Universal History (Sale et al) ・ Universal Hits-Golden Best ・ Universal Home API Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Universal hashing ： ウィキペディア英語版 Universal hashing In mathematics and computing universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of hash tables, randomized algorithms, and cryptography. == Introduction == Assume we want to map keys from some universe $U$ into $m$ bins (labelled $()\; =\; \backslash$). The algorithm will have to handle some data set $S\; \backslash subseteq\; U$ of $|S|=n$ keys, which is not known in advance. Usually, the goal of hashing is to obtain a low number of collisions (keys from $S$ that land in the same bin). A deterministic hash function cannot offer any guarantee in an adversarial setting if the size of $U$ is greater than $m\; \backslash cdot\; n$, since the adversary may choose $S$ to be precisely the preimage of a bin. This means that all data keys land in the same bin, making hashing useless. Furthermore, a deterministic hash function does not allow for ''rehashing'': sometimes the input data turns out to be bad for the hash function (e.g. there are too many collisions), so one would like to change the hash function. The solution to these problems is to pick a function randomly from a family of hash functions. A family of functions $H\; =\; \backslash$ is called a universal family if, $\backslash forall\; x,\; y\; \backslash in\; U,\; ~\; x\backslash ne\; y:\; ~~\; \backslash Pr\_\; (=\; h(y))\; \backslash le\; \backslash frac$. In other words, any two keys of the universe collide with probability at most $1/m$ when the hash function $h$ is drawn randomly from $H$. This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. Sometimes, the definition is relaxed to allow collision probability $O(1/m)$. This concept was introduced by Carter and Wegman〔 〕 in 1977, and has found numerous applications in computer science (see, for example 〔 〕). If we have an upper bound of on the collision probability, we say that we have $\backslash epsilon$-almost universality. Many, but not all, universal families have the following stronger uniform difference property: : $\backslash forall\; x,y\backslash in\; U,\; ~\; x\backslash ne\; y$, when $h$ is drawn randomly from the family $H$, the difference $h(x)-h(y)\; ~\backslash bmod~\; m$ is uniformly distributed in $()$. Note that the definition of universality is only concerned with whether $h(x)-h(y)=0$, which counts collisions. The uniform difference property is stronger. (Similarly, a universal family can be XOR universal if $\backslash forall\; x,y\backslash in\; U,\; ~\; x\backslash ne\; y$, the value $h(x)\; \backslash oplus\; h(y)\; ~\backslash bmod~\; m$ is uniformly distributed in $()$ where $\backslash oplus$ is the bitwise exclusive or operation. This is only possible if $m$ is a power of two.) An even stronger condition is pairwise independence: we have this property when $\backslash forall\; x,y\backslash in\; U,\; ~\; x\backslash ne\; y$ we have the probability that $x,y$ will hash to any pair of hash values $z\_1,\; z\_2$ is as if they were perfectly random: $P(h(x)=z\_1\; \backslash land\; h(y)=z\_2)=\; 1/m^2$. Pairwise independence is sometimes called strong universality. Another property is uniformity. We say that a family is uniform if all hash values are equally likely: $P(h(x)=z)=1/m$ for any hash value $z$. Universality does not imply uniformity. However, strong universality does imply uniformity. Given a family with the uniform distance property, one can produce a pairwise independent or strongly universal hash family by adding a uniformly distributed random constant with values in $()$ to the hash functions. (Similarly, if $m$ is a power of two, we can achieve pairwise independence from an XOR universal hash family by doing an exclusive or with a uniformly distributed random constant.) Since a shift by a constant is sometimes irrelevant in applications (e.g. hash tables), a careful distinction between the uniform distance property and pairwise independent is sometimes not made.〔 〕 For some applications (such as hash tables), it is important for the least significant bits of the hash values to be also universal. When a family is strongly universal, this is guaranteed: if $H$ is a strongly universal family with $m=2^L$, then the family made of the functions $h\; \backslash bmod\}$ fails to be universal. UMAC and Poly1305-AES and several other message authentication code algorithms are based on universal hashing.〔 David Wagner, ed. ("Advances in Cryptology - CRYPTO 2008" ). p. 145. 〕〔 Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. ("The Hash Function BLAKE" ). 2014. p. 10. 〕 In such applications, the software chooses a new hash function for every message, based on a unique nonce for that message. Several hash table implementations are based on universal hashing. In such applications, typically the software chooses a new hash function only after it notices that "too many" keys have collided; until then, the same hash function continues to be used over and over. (Some collision resolution schemes, such as dynamic perfect hashing, pick a new hash function every time there is a collision. Other collision resolution schemes, such as cuckoo hashing and 2-choice hashing, allow a number of collisions before picking a new hash function). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Universal hashing」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.